package com.leetcode;


import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Random;

/**
 * 1157. 子数组中占绝大多数的元素 (困难)
 * 设计一个数据结构，有效地找到给定子数组的 多数元素 。
 * 子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。
 * 实现 MajorityChecker 类:
 * - MajorityChecker(int[] arr) 会用给定的数组 arr 对 MajorityChecker 初始化。
 * - int query(int left, int right, int threshold) 返回子数组中的元素  arr[left..
 * .right] 至少出现 threshold 次数，如果不存在这样的元素则返回 -1。
 */
public class LeetCode1157 {

    public static void main(String[] arg0) {
        String testStr = "a";
    }


    /**
     * 内部类
     */
    class MajorityChecker {

        private int[] data;

        public static final int K = 20;
        private int[] arr;
        private Map<Integer, List<Integer>> loc;
        private Random random;

        public MajorityChecker(int[] arr) {
            data = arr;

            this.arr = arr;
            loc = new HashMap<>();
            for (int i = 0; i < arr.length; i++) {
                loc.putIfAbsent(arr[i], new ArrayList<>()); // 如果不存在键 arr[i] ，先put进去一个空集合作为值
                loc.get(arr[i]).add(i); // 值中的集合存放这个数在数组中的下标位置
            }
            random = new Random();
        }

        /**
         * [left, right] 的众数次数要大于等于 threshold
         */
        public int query(int left, int right, int threshold) {
            // 这种简单的处理会超时，需要在构造方法中对arr处理，转换为其它数据结构，在query中快速的拿出结果
            /*if (left >= 0 && right < data.length) {
                Map<Integer, Integer> counts = new HashMap<>();
                for (int i = left; i <= right; i++) {
                    int count = counts.getOrDefault(data[i], 0) + 1;
                    if (count >= threshold) {
                        return data[i];
                    }
                    counts.put(data[i], count);
                }
            }*/


            int length = right - left + 1;

            for (int i = 0; i < K; ++i) {
                int x = arr[left + random.nextInt(length)];
                List<Integer> pos = loc.get(x);
                int occ = searchEnd(pos, right) - searchStart(pos, left);
                if (occ >= threshold) {
                    return x;
                } else if (occ * 2 >= length) {
                    return -1;
                }
            }

            return -1;
        }

        private int searchStart(List<Integer> pos, int target) {
            int low = 0, high = pos.size();
            while (low < high) {
                int mid = low + (high - low) / 2;
                if (pos.get(mid) >= target) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            return low;
        }

        private int searchEnd(List<Integer> pos, int target) {
            int low = 0, high = pos.size();
            while (low < high) {
                int mid = low + (high - low) / 2;
                if (pos.get(mid) > target) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            return low;
        }
    }


}
